#ifndef SPLAY_H
#define SPLAY_H

#pragma once
#include <QDebug>
#include <new>

//****************************  genSplay.h  ****************************
//using namespace std;  // 添加这行
//template<class T> class SplayTree; // 下面都有了，不知道为什么要加这行...

template<class T>
class SplayingNode {
public:
    SplayingNode() {
        left = right = parent = 0;
    }
    SplayingNode(const T& el, SplayingNode* l = 0, SplayingNode* r = 0, SplayingNode* p = 0) {
        info = el; left = l; right = r; parent = p;
    }
    T info;
    SplayingNode* left, * right, * parent;
};

template<class T>
class SplayTree {
public:
    SplayTree() {
        root = 0;
    }
    void inorder() {
        inorder(root);
    }
    T* search(const T&);
    void insert(const T&);
protected:
    SplayingNode<T>* root;
    void rotateR(SplayingNode<T>*);
    void rotateL(SplayingNode<T>*);
    void continueRotation(SplayingNode<T>* gr, SplayingNode<T>* par,
        SplayingNode<T>* ch, SplayingNode<T>* desc);
    void semisplay(SplayingNode<T>*);
    void inorder(SplayingNode<T>*);
    void virtual visit(SplayingNode<T>*) {
    }
};


template<class T>
void SplayTree<T>::continueRotation(SplayingNode<T>* gr, SplayingNode<T>* par,
    SplayingNode<T>* ch, SplayingNode<T>* desc) {
    // 如果 p/child 有 祖父grandparent
    if (gr != 0) {
        // 根据原来父parent的位置，将其换为子child
        if (gr->right == ch->parent)
            gr->right = ch;
        else gr->left = ch;
    }
    // 如果没有祖父，那么新子child篡位到父parent的位置，成为根节点root
    else root = ch;
    // 如果p/child有孩子，其给新的儿parent托管
    if (desc != 0)
        desc->parent = par;
    // 认新的爹
    par->parent = ch;
    ch->parent = gr;
}

template<class T>
void SplayTree<T>::rotateR(SplayingNode<T>* p) {
    p->parent->left = p->right;
    p->right = p->parent;
    continueRotation(p->parent->parent, p->right, p, p->right->left);
}

template<class T>
void SplayTree<T>::rotateL(SplayingNode<T>* p) {
    p->parent->right = p->left;
    p->left = p->parent;
    continueRotation(p->parent->parent, p->left, p, p->left->right);
}

template<class T>
// 将节点移到树的根部root
void SplayTree<T>::semisplay(SplayingNode<T>* p) {
    while (p != root) {
        if (p->parent->parent == 0)    // if p's parent is the root;
            if (p->parent->left == p)
                rotateR(p);
            else rotateL(p);
        else if (p->parent->left == p) // if p is a left child;
            // 1. LL  左左情况，进行一次右旋即可
            if (p->parent->parent->left == p->parent) {
                rotateR(p->parent);
                p = p->parent;
            }
            // 2. RL  右左情况，先右旋，再左旋
            else {
                rotateR(p); // rotate p and its parent;
                rotateL(p); // rotate p and its new parent;
            }
        else                          // if p is a right child;
            // 3. RR  右右情况，进行一次左旋即可
            if (p->parent->parent->right == p->parent) {
                rotateL(p->parent);
                p = p->parent;
            }
            // 4. LR  左右情况，先左旋，再右旋
            else {
                rotateL(p); // rotate p and its parent;
                rotateR(p); // rotate p and its new parent;
            }
        if (root == 0)              // update the root;
            root = p;
    }
}

template<class T>
T* SplayTree<T>::search(const T& el) {
    SplayingNode<T>* p = root;
    while (p != 0)
        if (p->info == el) {        // 单词存在
            semisplay(p);           // 调用函数向上伸展到根部
            return &p->info;
        }
        else if (el < p->info)
            p = p->left;
        else p = p->right;
    return 0;
}

// 插入节点
template<class T>
void SplayTree<T>::insert(const T& el) {
    SplayingNode<T>* p = root, * prev = 0, * newNode;
    while (p != 0) {  // find a place for inserting a new node;
        prev = p;
        if (el < p->info)
            p = p->left;
        else p = p->right;
    }
    if ((newNode = new SplayingNode<T>(el, 0, 0, prev)) == 0) {
        qCritical() << "No room for new nodes\n";  // 内存不足，分配内存失败？
        throw std::bad_alloc();
    }
    if (root == 0)    // the tree is empty;
        root = newNode;
    else if (el < prev->info)
        prev->left = newNode;
    else prev->right = newNode;
}

// 中序遍历
template<class T>
void SplayTree<T>::inorder(SplayingNode<T>* p) {
    if (p != 0) {
        inorder(p->left);
        visit(p);
        inorder(p->right);
    }
}

#endif // WORDSPLAY_H
